import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * User: 花海
 * Date: 2022-09-28
 * Time: 11:27
 */
public class tree {
    static class treenode{
        char val;
        treenode left;
        treenode right;
        treenode(char val){
            this.val=val;

        }


    }
    tree(){



    }
    public  static void DisplayTree(treenode root){

        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        DisplayTree(root.left);
        DisplayTree(root.right);

    }
    public static int nodeSize;

    /**
     * 获取树中节点的个数：遍历思路
     */
    static void  size(treenode root) {
        if(root==null){
            return;
        }else{
            nodeSize++;
        }
        size(root.left);
        size(root.right);

    }
    static int  size2(treenode root){
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;//左加右加自身
    }

    public  static treenode CreatTree(){
         treenode A=new treenode('A');
         treenode B=new treenode('B');
         treenode C=new treenode('C');
         treenode D=new treenode('D');
         treenode E=new treenode('E');
         treenode F=new treenode('F');
         treenode G=new treenode('G');
         treenode H=new treenode('H');
         A.left=B;
         A.right=C;
         B.left=D;
         B.right=E;
         E.right=H;
         C.left=F;
         C.right=G;
         return A;


     }
    public static int leafSize = 0;

    static void getLeafNodeCount1(treenode  root) {
        //获取二叉树中叶子的个数,用遍历法
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }
    /*
    获取叶子节点的个数：子问题
    */
    static int getLeafNodeCount2 (treenode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

   static int getKLevelNodeCount(treenode root, int k) {
        //获取第k层元素个数
       if(root==null){
           return 0;//没有树节点返回0

       }
       if(k==1){
           return 1;//找到k层 返回自身的数量
       }
       return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
   static int getHeight(treenode root) {
        //获取二叉树的高度
       if(root==null){
           return 0;
       }
       return getHeight(root.left)>getHeight(root.right)?getHeight(root.left)+1:getHeight(root.right)+1;

    }
    //寻找树中有没有val值
   static treenode find(treenode root, char val) {
        if(root.val==val){
            return root;
        }
        if(root==null){
            return null;
        }
      treenode ret = find(root.left, val);
       if (ret != null) {
           return ret;
       }
       ret = find(root.right, val);
       if (ret != null) {
           return ret;
       }
       return null;



    }
    //层序遍历
   static void levelOrder(treenode root){
        Queue<treenode>qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            treenode cur=qu.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                qu.offer(cur.left);

            }
            if(cur.right!=null){
                qu.offer(cur.right);

            }
        }
    }



    public static void main(String[] args) {
      treenode root=  CreatTree();
      DisplayTree(root);
        System.out.println();
      size(root);
      getLeafNodeCount1(root);
        System.out.println("this tree has "+nodeSize+"treenode");
        System.out.println("this tree has "+size2(root)+"treenode");
        System.out.println("this tree has "+leafSize+"leave");
        System.out.println("this tree has "+getLeafNodeCount2(root)+"leave");
        System.out.println("this tree high "+getHeight(root));
        levelOrder(root);











    }
}
